/*
 *https://leetcode.cn/problems/edit-distance/description/
 *72. 编辑距离
 *medium, 吴朝泽 2024.9.6
 *动态规划
f[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符的最小编辑距离。
如果 word1 为空串（即 i = 0），将 word2 的前 j 个字符插入到 word1 中。此时 f[0][j] 的值为 j。
如果 word2 为空串（即 j = 0），将 word1 的前 i 个字符删除。此时 f[i][0] 的值为 i。
当 word1[i-1] == word2[j-1] 时，f[i][j] 等于 f[i-1][j-1]，因为这两个字符相同，不需要额外的操作。
当 word1[i-1] != word2[j-1] 时，可以有三种操作：
插入：将 word2[j-1] 插入到 word1 中，相当于计算 f[i][j-1] 后再加 1。
删除：从 word1 中删除 word1[i-1]，相当于计算 f[i-1][j] 后再加 1。
替换：将 word1[i-1] 替换成 word2[j-1]，相当于计算 f[i-1][j-1] 后再加 1。
*/

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        int f[m + 1][n + 1];
        for (int j = 0; j <= n; ++j) 
            f[0][j] = j;
        
        for (int i = 1; i <= m; ++i) 
        {
            f[i][0] = i;
            for (int j = 1; j <= n; ++j)
             {
                if (word1[i - 1] == word2[j - 1])
                    f[i][j] = f[i - 1][j - 1];
                else 
                    f[i][j] = min({f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]}) + 1;
            }
        }
        return f[m][n];
    }
};